1) Field of the Invention
The present invention relates to a method of and an apparatus for translating a virtual address into a physical address in a computer system of a virtual storage system.
2) Description of the Related Art
In a computer of a virtual storage system, a list called a page table is prepared to carry out address translation from a virtual address (VA) to a physical address (PA).
The address translation will be explained below with reference to FIG. 7. FIG. 7 shows a computer system of a virtual storage system. In this computer system, a CPU (central processing unit) 10 executes various operation instructions by making access to a main storage apparatus 20.
The main storage apparatus 20 stores a page table 30 for translating the virtual address VA into the physical address PA. The virtual address VA is an address specified in a computer program. On the other hand, the physical address PA is an address allocated to a physical memory unit in the main storage apparatus 20.
The page table 30 is a table that relates the virtual address VA to the physical address PA. In FIG. 7, the virtual address VA and the physical address PA are expressed in hexadecimal numbers like “aaaa 0000 0000 0000.”
The virtual address VA has a 64-bit structure <63:0> (i.e., bits 0 to 63), as shown in FIG. 8A. In the virtual address VA <63:0>, VA <12:0> is an offset value having a 13-bit structure (hereinafter to be described as Off-SET <12:0>).
VA <21:13> is a RAM access address having a 9-bit structure (hereinafter to be described as RAM-ACCS-ADRS <8:0>). This RAM-ACCS-ADRS <8:0> is an address in a TLB (translation look-aside buffer: address translation buffer) 40 to be described later shown in FIG. 7, and corresponds to RAM-ACCS-ADRS <8:0> shown in FIG. 7.
Referring back to FIG. 8A, VA <63:22> is a tag having a 42-bit structure (hereinafter to be described as TLB-TAG <41:0>; refer to FIG. 9A), and this is used as an index in the TLB 40. Further, TLB-TAG <41:0> shown in FIG. 8A corresponds to TLB-TAG <41:0> in the TLB 40.
On the other hand, the physical address PA in the page table 30 shown in FIG. 7 has a 43-bit structure <42:0>, as shown in FIG. 8B. In this physical address PA <42:0>, PA <12:0> is an offset value having a 13-bit structure (hereinafter to be described as Off-SET <12:0>), and this is equivalent to Off-SET <12:0> shown in FIG. 8A. PA <42:13> is data corresponding to the physical address (hereinafter to be described as TLB-DATA <29:0>).
When there is no TLB 40, in principle, an instruction processing section (not shown) of the CPU 10 must make access to the main storage apparatus 20 and translate the virtual address VA into the physical address PA with reference to the page table 30, by using the virtual address VA, each time when it is necessary to carry out the address translation.
However, when the CPU 10 makes access to the main storage apparatus 20 and refers to the page address 30 at each time of the address translation, much processing time is required for the address translation. This has a problem that the processing speed is lowered.
In order to avoid this problem, conventionally, the TLB (address translation buffer) 40 has been provided in a not shown RAM (random access memory) that can be accessed at a high speed, within the CPU 10.
This TLB 40 has 512 entries, for example. Assume that, in the TLB 40, values are expressed in hexadecimal numbers such as “0000” and “2aaa 8000 0000”. In each entry of the TLB 40, there are stored RAM-ACCS-ADRS <8:0> that shows an address (entry) in the RAM, TLB-TAG <41:0> (tag) as an index, and TLB-DATA <29:0> (data) corresponding to the physical address, as TLB data respectively.
TLB-TAG <41:0> in the TLB 40 corresponds to TLB-TAG <41:0> in the virtual address VA. TLB-DATA <29:0> in the TLB 40 corresponds to TLB-DATA <29:0> in the physical address PA.
In the above structure, in order to read an instruction code from the main storage apparatus 20, the instruction processing section of the CPU 10 refers to the TLB 40, by using RAM-ACCS-ADRS <8:0> included in the virtual address VA corresponding to this instruction code as a RAM access address.
Based on this, TLB-TAG <41:0> and TLB-DATA <29:0> stored at the address shown by RAM-ACCS-ADRS <8:0> (refer to FIG. 8A) are read out.
The instruction processing section compares the above TLB-TAG <41:0> with TLB-TAG <41:0> included in the virtual address VA.
When both TLB-TAG <41:0> coincide with each other, the instruction processing section combines the above TLB-DATA <29:0> with Off-SET <12:0> included in the virtual address VA, as HIT (TLB hit), and generates the physical address PA.
The instruction processing section reads the instruction code from the main storage apparatus 20 based on the physical address PA.
The instruction processing section executes the instruction based on the instruction code. At the time of storing a result of the execution into the main storage apparatus 20, the instruction processing section refers to the TLB 40 again, and executes the address translation processing to translate the virtual address VA into the physical address PA.
When TLB-TAG <41:0> of the TLB 40 does not coincide with TLB-TAG <41:0> included in the virtual address VA, (MISS (TLB error), the instruction processing section refers to the page table 30, and translates the virtual address VA into the physical address PA.
When the TLB error has occurred, RAM-ACCS-ADRS <8:0> and TLB-TAG <41:0> included in the virtual address VA, and TLB-DATA <29:0> included in the physical address PA, are stored as TLB data in a pair, into the TLB 40.
Thereafter, the virtual address VA is translated into the physical address PA based on the TLB 40. When there is no space in the TLB 40, the data is overwritten onto an entry where the oldest TLB data is stored.
At this time, conventionally, a two-layer address translation apparatus is used to achieve a high-speed address translation using the TLB in two layers of a lower layer and a higher layer. FIG. 10 is a block diagram that shows a structure of a conventional two-layer address translation apparatus 50.
The two-layer address translation apparatus 50 shown in FIG. 10 has a two-layer structure including a lower address translator 51 and a higher address translator 52. Actually, the two-layer address translation apparatus 50 constitutes a part of the processor like the CPU. The lower address translator 51 translates the virtual address into the physical address by using a lower TLB (not shown) having the same structure as that of the TLB 40 (refer to FIG. 1).
The higher address translator 52 stores a part of the TLB data out of the TLB data stored in the lower TLB of the lower address translator 51. The higher address translator 52 can carry out the processing at a higher speed than the lower address translator 51.
uTLB_GO (a higher access request signal) is a signal that shows that the virtual address VA has been output to the higher address translator 52, that is, an access to the higher address translator 52 has been requested.
When UTLB_GO (a higher access request signal) and the virtual address VA have been input, the higher address translator 52 searches the higher TLB by using TLB-TAG <41:0> included in the virtual address VA. When the searching HITs (higher TLB hit), the higher address translator 52 translates the virtual address VA into the physical address PA by using the higher TLB.
When the searching of the higher TLB has not hit, that is, when the searching has been MISS (higher TLB error), the higher address translator 52 outputs mTLB_GO (a lower access request signal) to make the lower address translator 51 carry out the address translation.
When mTLB_GO (a lower access request signal) and the virtual address VA have been input, the lower address translator 51 searches the lower TLB, and translates the virtual address VA into PA (the physical address).
When the lower address translator 51 has been able to translate the virtual address VA into the physical address PA, that is, when the lower access has been HIT (lower TLB hit), the lower address translator 51 outputs a write enable signal WE and a write data WD to the higher address translator 52.
The write data WD is constructed of a virtual address VA <63:13> and a physical address PA <42:13> corresponding to the HIT (lower TLB hit), as shown in FIG. 11. On the other hand, the write enable signal WE is a signal for instructing the writing of the write data WD to the higher TLB of the higher address translator 52.
When the lower address translator 51 has not been able to translate the virtual address VA into the physical address PA, that is, when the lower access has been MISS (lower TLB error), the address translation is executed based on the page table (not shown).
In the above structure, when the virtual address VA and uTLB_GO (a higher access request signal) shown in FIG. 10 have been input to the higher address translator 52, the higher address translator 52 compares VA <63:13> with the virtual address VA <63:13> stored in the higher TLB (refer to FIG. 9A).
When both VA <63:13> coincide with each other, HIT (higher TLB hit) occurs. The higher address translator 52 combines VA <12:0> and TLB-DATA <29:0> stored in TLB together, and outputs PA <42:0> (physical address) shown in FIG. 8B.
Based on the above PA (physical address), the instruction code is read from the main storage apparatus (not shown).
When VA <63:13> does not coincide with each other, MISS (higher TLB error) occurs. Based on this, the higher address translator 52 outputs mTLB_GO (a lower access request signal) to the lower address translator 51. Further, the virtual address VA is input to the lower address translator 51.
The lower address translator 51 searches the lower TLB based on the virtual address VA, in a similar manner to that of the higher address translator 52.
When it has been possible to translate the virtual address VA into the physical address PA, that is, when the access has been HIT (lower TLB hit), the lower address translator 51 outputs the write enable signal WE and the write data WD (the virtual address VA <63:13> and the physical address PA <42:13>) shown in FIG. 11 to the higher address translator 52.
The higher address translator 52 stores the virtual address VA <63:13> and the physical address PA <42:13> obtained from the write data WD to the higher TLB. Thereafter, the higher address translator 52 translates the virtual address VA into the physical address PA.
According to the conventional two-layer address translation apparatus 50, there have been the following problems. When the same virtual address VA and uTLB_GO (a higher access request signal) have been input to the higher address translator 52 as MISS (higher TLB error) continuously by two or more times, the same write data WD (the virtual address VA <63:13> and the physical address PA <42:13>) are stored in the higher TLB in a duplicate state. As a result, a multi-hit has occurred.
In other words, at the first time, the virtual address VA and uTLB_GO (a higher access request signal) are input to the higher address translator 52. Because of MISS (higher TLB error), mTLB_GO (a lower access request signal) and the virtual address VA are input to the lower address translator 51. At this time, the lower address translator 51 searches the lower TLB, and HIT (lower TLB hit) occurs.
As a result, the lower address translator 51 outputs the write data WD (the virtual address VA <63:13> and the physical address PA <42:13>) to the higher address translator 52, and stores the data into the higher TLB.
However, when the virtual address VA and uTLB_GO (a higher access request signal) that are the same as the first-time virtual address VA are input at a second time, during a period from when the virtual address VA and uTLB_GO (a higher access request signal) have been input to the higher address translator 52 at the first time till when the write data WD has been input to the higher address translator 52 (before the write data WD is written to the higher TLB), MISS (higher TLB error) occurs because of two continuous errors.
Consequently, mTLB_GO (a lower access request signal) and the virtual address VA are input to the lower address transistor 51. At this time, the lower address translator 51 searches the lower TLB, and HIT (lower TLB hit) occurs again as two continuous HIT.
Next, the lower address translator 51 outputs the second-time write data WD (the virtual address VA <63:13> and the physical address PA <42:13>) that are the same as the first-time data to the higher address translator 52, and stores the data into the higher TLB.
At this time, the first-time write data WD and the second-time write data WD that are the same write data WD are stored in the higher TLB in duplicate. When the virtual address VA and uTLB_GO (a higher access request signal) are input to the higher address translator 52 at a third time in this state, a multi-hit occurs, which becomes an error.